package org.gzc.sort;

import java.util.Arrays;

/**
 * @Description: 插入排序
 * @Author: guozongchao
 * @Date: 2020/8/8 15:03
 */
public class InsertSort implements SortStrategy{
    @Override
    public void sort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int insertVal = array[i];    //临时存放每一趟需要比较的值
            int insertIndex=i-1;    //存放需要比较值的前一个值的下标
            while (insertIndex >= 0 && insertVal < array[insertIndex]) {  //在没有越界的情况下，如果插入值比前一项值小，则需要将前一项后移
                array[insertIndex + 1] = array[insertIndex];   //后移一个位置
                insertIndex--;
            }

            //如果比较后，前一项没有后移，则说明插入值比前面所有值都大，则不需要执行这一步骤，直接进行下一趟比较
            if (insertIndex + 1 != i) {
                array[insertIndex+1]=insertVal;
            }
            //System.out.println("第"+i+"趟结果："+ Arrays.toString(array));
        }
    }
}
